\section{Discussions}
\label{sec:discussions}

In this paper, we considered the problem of selecting a diverse and representative subset
from a large corpus of items. We modeled each item as being decorated by a set of features,
and the goal was to ensure that the selected subset of items achieved large coverage on all
features. We discussed various problem formulations representing this goal, and studied
both the online and offline versions of the problem. Our key technical contribution was 
an easily implementable and scalable online algorithm for this problem. We analyzed this
algorithm using theoretical techniques and showed that it achieves an approximation ratio of
(roughly) 50\%. We also performed wide-scale experiments on a variety of real-world and 
synthetically generated data sets and concluded that the algorithm performs even
better than its theoretical guarantees in practice, and also confirmed that it outperforms
several natural and intuitive algorithms for this problem by a wide margin.

In fact, our algorithm adapts well to several real-world complications.
For example, consider a data set that has {\em outliers}, i.e. some features that are very sparse. 
Our experimental results on the sorted coverage values show that in such cases, not only is the algorithm able to obtain near-optimal minimum coverage, but also does well on all features that have low coverage. This is crucial in situations where we do not want to maximize minimum coverage only, but also want to ensure that the algorithm performs well with respect to more relaxed notions of diversity, e.g. the coverage on the bottom 10\% of features. This was in fact the case with our real data set, and here the diversifier algorithm performed particularly well. The algorithm is also extremely efficient and at each online stage, it only needs time proportional to the number of features to compute if a threshold is satisfied by the new arriving item; since it is very efficient, we do not plot graphs with running times, but the algorithm clearly scales to extremely large data sets as shown in our experiments. 
%In particular for the real data set, as stated before, we ran experiments on over 100 data sets %each of about a size of $1M$ items and $18$ features. 

%There are a couple of directions to take this work further, which also the algorithm can adapt to. 
In real-world applications, it is often the case that all items are not of identical {\em quality}, and while we wish to select a set of items that are diverse in terms of their feature coverage, we would also like to ensure that that these selected items have high overall quality. In such situations, we may interpret the quality of items as an additional feature on which we also want to meet a given quality target. Alternatively, we may opt to set a quality threshold on items and not select any item that does not meet this threshold irrespective of the coverage it achieves on the set of features. Other applications may have more complicated quality requirements, and it is an interesting direction of future research is to investigate the impact of item quality on the diversification problem.

In some other situations, items cover their constituent features to different degrees that may be represented by {\em coverage weights} (typically in the range $[0,1]$). It can in fact be shown  that the same approximation guarantees hold from a theoretical perspective for this more general situation by using a slightly modified algorithm (for simplicity we omit these details). Even from an experimental standpoint, since the algorithm does well on features that are sparsely populated, it is expected to handle data sets with weighted coverages without a significant degradation in performance. However, further experimental work in this direction is desirable.

Yet another possibility is that features not only have a target coverage that we would like to achieve, but also an upper limit on coverage. Such two-sided errors can be handled by pretending to duplicate each feature by adding a compliment with the corresponding complemented coverage target. 

Finally, in certain situations, the coverage function on a feature may not be additive, i.e. the overall coverage obtained by a set of items on a feature may be different from the sum of their individual coverage weights for the feature. An open problem is to design algorithms that are capable of handling such general coverage functions.
